Greg Detre
09:30 Thursday, September 12, 2002
searching through a space of possible solutions, and you want to find the best one
set of states����� S
operators���������� S�S
cost/utility������� S�R
there�s no notion of a path length � you just want the best one (according to your cost function)
solution-space search � made-up term
e.g. travelling salesman
some versions you can/can�t revisit cities
all permutations of cities
can hope that similar permutations will have similar values, and so try and make incremental improvements
risk of being stuck in local maximum
one way to deal with this is to randomly re-start
simulated annealing � sometimes accept changes that aren�t improving
temperature decreases over time, so you start bouncing crazily, and hope to end up near the best solution, and then slowly make smaller changes, which sometimes involve small decreases, but eventually settles somewhere that you hope is pretty optimal
in a continuous space, often use gradient descent
compute the gradient of your position
take little steps towards the highest position, but you have the same problems with local optima
it�s raining = all possible worlds in which it�s raining
you don�t ever want to enumerate that set of possible worlds
logic allows you to talk about this set of possible raining worlds without enumerating it
syntax:�������������� what expressions are legal
semantics:�������� what legal expressions mean
proof system:�� way of manipulating the syntax that respects semantics
sentence (well-formed formula) � the following are sentences:
true and false are sentences
propositional variables, e.g. P, Q, Raining
if y and f are sentences, then so are:
(y), (�/span>y), (y �/span> f), (y �/span> f), (f � y), (f � y)
nothing else is a sentence
�/span> �/span> �/span> � �
the meaning of a sentence is truth value: t or f
true or false, with respect to an interpretation
an interpretation is an assignment of truth values to propositional variables
╞ i f�������������������� sentence f has truth value t in interpretation i
╞NOT i f��������������� sentence f has truth value f in interpretation i
╞ i true��������������� for all i
╞
i NOT false�������� for
all i
╞ i P�������������������� iff i(P) = t� for all propositional variables P
╞
i �/span>f���������������� iff ╞ i NOT f��������������������������������������������� ����������������������������������� for all sentences f and y
╞
i f
�/span>
y����������� iff ╞
i f
and ╞ i y��������������������������������� ����������������������������������� for all
sentences f and y
╞
i f
�/span>
y����������� iff ╞
i f
or ╞ i y������� (non-exclusive)���������������������������� for all sentences f and y
╞
i (f)����������������� iff
╞ i f
f � y��������������� (�/span>f �/span> y)
f � y��������������� (f � y) �/span> (y �
f)
a sentence f is valid iff ╞ i (f) for all i�������������������� ���������������������������� true, �/span>false, P �/span> �/span>P
a sentence f is satisfiable iff ╞ i (f) for some i����� ���������������������������� P, true
a sentence f is unsatisfiable iff there is no i such that ╞ i (f)�������� false, P �/span> �/span>P
smoke � smoke
valid, because no matter what interpretation of smoke (i.e. whichever truth values the propositional variables have), it�s true
smoke � fire
satisfiable, because it�s true if smoke is true and fire is true
it�s not valid though, because if smoke is true and fire is false, then the sentence is false
s���� f������������ (s � f) � ( NOTf -> NOTs)
t����� t������������ t�������������������������� f����� f������������ t������������������� ������ t
t����� f������������ f�������������������������� t����� f������������ f������������������� ������ t
f����� t������������ t�������������������������� f����� t������������ t������������������� ������ t
f����� f������������ f�������������������������� t����� t������������ t������������������� ������ t
������ valid
(s -> f) -> (NOT s -> NOT f)
t������������������������������������������������������� ������ t
t������������������������������������������������������� ������ f
f������������������������������������������������������� ������ t
t������������������������������������������������������� ������ f
������ satisfiable
moving from (s -> f) to (NOT f -> NOT s) is called the contrapositive